#include <iostream>
#include "./mgraph.h"
#include "../../stack/model/cir-queue.h"

using namespace std;

void createGraph(MGraph &graph, DirectType directType, WeightType weightType)
{
	graph.directType = directType;
	graph.weightType = weightType;
}

int locateVex(MGraph &graph, VertexType u)
{
	for (int i = 0; i < graph.vexNum; i++)
	{
		if (graph.vex[i] == u)
		{
			return i;
		}
	}
	return -1;
}

int isConnected(MGraph &graph, int v, int w)
{
	return (graph.weightType == TYPE_GRAPH && graph.edge[v][w] != 0) || (graph.weightType == TYPE_NET && graph.edge[v][w] != INFINITY);
}

int firstAdjVex(MGraph &graph, int v)
{
	for (int i = 0; i < graph.vexNum; i++)
	{
		if (isConnected(graph, v, i))
		{
			return i;
		}
	}
	return -1;
}

int nextAdjVex(MGraph &graph, int v, int w)
{
	for (int i = w + 1; i < graph.vexNum; i++)
	{
		if (isConnected(graph, v, i))
		{
			return i;
		}
	}
	return -1;
}

void insertVex(MGraph &graph, VertexType v)
{
	graph.vex[graph.vexNum] = v;
	graph.vexNum++;
	// 修改邻接矩阵
	for (int i = 0; i < graph.vexNum - 1; i++)
	{
		graph.edge[i][graph.vexNum - 1] = (graph.weightType == TYPE_GRAPH || i == graph.vexNum - 1) ? 0 : INFINITY;
	}
	for (int i = 0; i < graph.vexNum; i++)
	{
		graph.edge[graph.vexNum - 1][i] = (graph.weightType == TYPE_GRAPH || i == graph.vexNum - 1) ? 0 : INFINITY;
	}
}

void deleteVex(MGraph &graph, int v)
{
	graph.vex[v] = 0;
	// 删除对应的弧
	for (int i = 0; i < graph.vexNum; i++)
	{
		if (isConnected(graph, v, i))
		{
			deleteArc(graph, v, i);
		}
	}
	// 顶点前移
	for (int i = v + 1; i < graph.vexNum; i++)
	{
		graph.vex[i - 1] = graph.vex[i];
	}
	// 邻接矩阵前移
	for (int i = 0; i < graph.vexNum; i++)
	{
		for (int j = v + 1; j < graph.vexNum; j++)
		{
			graph.edge[i][j - 1] = graph.edge[i][j];
		}
	}
	for (int i = 0; i < graph.vexNum; i++)
	{
		for (int j = v + 1; j < graph.vexNum; j++)
		{
			graph.edge[j - 1][i] = graph.edge[j][i];
		}
	}
	graph.vexNum--;
}

void insertArc(MGraph &graph, int v, int w, int weight)
{
	int alreadyConnect = isConnected(graph, v, w);
	graph.edge[v][w] = weight;
	if (graph.directType == UN_DIRECT)
	{
		graph.edge[w][v] = weight;
	}
	if (!alreadyConnect)
	{
		graph.arcNum++;
	}
}

void deleteArc(MGraph &graph, int v, int w)
{
	int isConnect = isConnected(graph, v, w);
	graph.edge[v][w] = (graph.weightType == TYPE_GRAPH) ? 0 : INFINITY;
	if (graph.directType == UN_DIRECT)
	{
		graph.edge[v][w] = (graph.weightType == TYPE_GRAPH) ? 0 : INFINITY;
	}
	if (isConnect)
	{
		graph.arcNum--;
	}
}

void DFS(MGraph &graph, int i, int *visited, void (*visit)(VertexType &))
{
	// 访问起始点
	visit(graph.vex[i]);
	visited[i] = 1;
	// 对未访问的邻接点递归调用
	for (int j = 0; j < graph.vexNum; j++)
	{
		if (isConnected(graph, i, j) && visited[j])
		{
			DFS(graph, j, visited, visit);
		}
	}
}

void DFSTraverse(MGraph &graph, void (*visit)(VertexType &))
{
	// 初始化访问辅助数组
	int *visited = (int *)calloc(graph.vexNum, sizeof(int));
	for (int i = 0; i < graph.vexNum; i++)
	{
		visited[i] = 0;
	}
	// 对未访问的顶点调用DFS
	for (int i = 0; i < graph.vexNum; i++)
	{
		if (!visited[i])
		{
			DFS(graph, i, visited, visit);
		}
	}
}

void BFSTraverse(MGraph &graph, void (*visit)(VertexType &))
{
	// 初始化辅助队列，辅助数组
	CircularQueue queue;
	initCircularQueue(queue);
	int *visited = (int *)calloc(graph.vexNum, sizeof(int));
	for (int i = 0; i < graph.vexNum; i++)
	{
		visited[i] = 0;
	}
	for (int i = 0; i < graph.vexNum; i++)
	{
		if (!visited[i])
		{
			// 先访问这个点
			visit(graph.vex[i]);
			visited[i] = 1;
			// 访问的顶点入队列（放入访问的点的索引）
			enterCircularQueue(queue, i);
			while (!circularQueueEmpty(queue))
			{
				i = goOutCircularQueue(queue);
				// 访问这个点的所有邻接点并入队列
				for (int j = 0; j < graph.vexNum; j++)
				{
					visit(graph.vex[j]);
					visited[j] = 1;
					enterCircularQueue(queue, j);
				}
			}
		}
	}
}

void printGraph(MGraph &graph)
{
	cout << "顶点：" << endl;
	for (int i = 0; i < graph.vexNum; i++)
	{
		cout << graph.vex[i] << " ";
	}
	cout << endl;
	cout << "邻接矩阵：" << endl;
	for (int i = 0; i < graph.vexNum; i++)
	{
		for (int j = 0; j < graph.vexNum; j++)
		{
			int weight = graph.edge[i][j];
			if (weight == INFINITY)
			{
				cout << "∞ ";
				continue;
			}
			cout << weight << " ";
		}
		cout << endl;
	}
}